class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if "**" in p:
            p = p.replace("**", "*")
        if p == "*":
            return True
        count, len_s = 0, len(s)
        while count < len(p):
            if p[count] == "?":
                count += 1
            elif p[count] == "*":
                for i in range(0, len_s - len(p) + p.count("*") + 1):
                    if self.isMatch(s[count+i:], p[count+1:]):
                        return True
                else:
                    return False
            else:
                if count > len_s - 1:
                    return False
                elif p[count] == s[count]:
                    count += 1
                else:
                    return False
        if count < len_s:
            return False
        elif count == len_s:
            return True
        else:
            return False

    def isMatch2(self, s: str, p: str) -> bool:
        # 处理一下p，可以减少动态规划的次数
        while "**" in p:
            p = p.replace("**", "*")
        if p == "*":
            return True
        len_s, len_p, dongtai_list = len(s), len(p), []
        # 初始化填充表格
        for i in range(len_p+1):
            dongtai_list.append([])
            for j in range(len_s+1):
                dongtai_list[i].append(False)
        # dongtai_list[i][j]表示s[j-1]和p[i-1]是否匹配
        # 0表示空字符，两个都是空应该匹配
        dongtai_list[0][0] = True
        # 初始化填充，只有当p第一个是“*”的时候s为空才能匹配
        for i in range(len_p):
            if p[i] == "*" and dongtai_list[i][0]:
                dongtai_list[i+1][0] = True
        # 开始动态规划，每次更新的格子是dongtai_list[i+1][j+1]
        for i in range(0, len_p):
            flag = False
            for j in range(0, len_s):
                if p[i] == "*" and (dongtai_list[i+1][j] or dongtai_list[i][j+1]):
                    dongtai_list[i+1][j+1] = True
                    flag = True
                else:
                    if dongtai_list[i][j] and (p[i] == s[j] or p[i] == "?"):
                        dongtai_list[i+1][j+1] = True
                        flag = True
                # 下面这几句测试用的
                # print(i, j)
                # for lists in dongtai_list:
                #     print(lists)
                # print("-------------")
            if not flag:
                break
        return dongtai_list[len_p][len_s]


a = Solution()
# print(a.isMatch2("bbaaaabaaaaabbabbabbabbababaabababaabbabaaabbaababababbabaabbabbbbbbaaaaaabaabbbbbabbbbabbabababaaaaa",
# "******aa*bbb*aa*a*bb*ab***bbba*a*babaab*b*aa*a****"))
print(a.isMatch2("aab", "c*a*b"))
